package 代码记录.校招笔试真题.笔试真题_2022.小米;

import java.util.*;

/**
 * 二叉搜索树转双向链表(牛客原题)
 */
public class Test2 {
    /**
     * 非虚拟头节点版
     * 因为牛客网上要求不能创建任何新的结点,所以虚拟头节点版本过不了
     * 为了过面试方便,这几道题统一记住非虚拟头节点版,虽然虚拟头节点版更短
     * 其实和力扣对比,牛客网的这道题不严谨,用我的方法做,它这道题是错的
     */
    TreeNode prev = null;
    TreeNode head = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }
        inOrder(pRootOfTree);
        return head;
    }
    private void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        if(prev != null) {
            prev.right = root;
        }else{
            head = root;
        }
        root.left = prev;
        prev = root;
        inOrder(root.right);
    }

    /**
     * @return 虚拟头节点版,但是牛客网过不了
     */
    //TreeNode prev = null;
    public TreeNode Convert2(TreeNode pRootOfTree) {
        if(pRootOfTree==null) {
            return null;
        }
        TreeNode dummy = new TreeNode(-1);
        prev = dummy;
        inOrder(pRootOfTree);
        return dummy.right;
    }
    private void inOrder2(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        prev.right = root;
        root.left = prev;
        prev = root;
        inOrder(root.right);
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}